1. Field of the Invention
This present invention may relate to a logic unit for the configuration of an architecture that is simultaneous-as-to-time and operable under the Byzantine algorithm and that tolerates a plurality F of faults, with a plurality of inputs for in-reading of data into registers of a set of registers and a plurality of outputs for out-reading of data from the registers, whereby each output is adapted to be connected with an input of a further logic unit. Furthermore, the present invention may relate to a computer unit with such logic unit, as well as to the fault tolerant assembly of at least 3F+1 logic units or computer units. Finally, the present invention may relates also to a method of operating a fault tolerant assembly with at least 3F+1 of such logic units or computer units with F+1 data distributing cycles.
2. Background Information
Fault tolerant computers of this type are known, for example, from German Patent No. 44 01 168 C2. They operate under the Byzantine algorithm as described in German Patent No. 44 01 168 C2, as well as in the paper by Leslie Lamport, Robert Shostak, and Marshall Pease, entitled xe2x80x9cThe Byzantine Generals Problemxe2x80x9d, ACM Transaction on Programming Languages and Systems (TOPLAS), Volume 4, Number 3, July 1982, pages 382-401. The Byzantine algorithm is comprised essentially of a redundant data processing with a plurality of computer units operating in parallel which under this algorithm distribute data, in a manner which will be explained in greater detail below, and compare the data. Fault tolerant computers of this type are comprised of an assembly of 3F+1 computer units RE1 to RE(3F+1). Such computer units are, for example, for F=1, in accordance with FIG. 5, connected to one another in such a manner so that each computer unit can directly exchange data with any other computer unit. By distribution into F+1 distribution cycles and verification of these data under the Byzantine algorithm, a fault-containing computer unit can hereby be recognized and deactivated, whereby the unaffected computer units continue to operate with valid data.
Each computer unit contains, for this purpose, one data storage DS1 to DS(3F+1). To make the basic problematic which is the base of the invention more clearly understood, the circuitry and procedures in such fault tolerant computers, on the basis of FIGS. 5, 5a, 5b and 5c of this application, will be briefly described for F=1, for example.
FIG. 5 of this application shows how, via process signal lines 1, 2, 3, 4, 5, process signals are passed to each computer unit RE1, RE2, RE3, RE4. Further data lines 6, 7, 8, 9, 10, 11 connect each computer unit with respectively one other computer unit. Each of these data lines 6-11 is comprised in detail of bi-directional connections for data and for deactivating signals and providing of clock pulse signals. The lines 1 to 11 shown in FIG. 5 are to be found in corresponding manner in the FIGS. 5a, 5b and 5c, but without reference numerals.
Each one of the four computer units RE1 to RE4 has a process interface PSS and a monitoring logic xc3x9cL, as well as an application specific processor AP. The data storages DS1 to DS4 are part of the monitoring logic xc3x9cL and serve for storing of in-read process data.
The original data produced in the computer unit or, respectively, data d1 to d4 in-read by a process interface PSS are initially taken up in the respectively associated data storages DS1 to DS4, in accordance with FIG. 5a. 
Subsequently, each computer unit transfers, in a first data distribution cycle in accordance with FIG. 5b, its original data d1 to d4 to each other computer unit, into the associated data storage. At the conclusion of this distribution cycle, thus, each data storage contains, in accordance with FIG. 5a, the in-read, inherent data d1; d2; d3; d4, as well as the d1/RE1; d2/RE2; d3/RE3; d4/RE4 identified data, respectively, of the other computer units.
In a second data distribution cycle in accordance with FIG. 5c, each computer unit then transfers all data obtained according to FIG. 5b into the data storages of those two computer units which did not already obtain data in the original condition in accordance with FIG. 5a. Thus, at the conclusion of this distribution cycle, each data storage DS1, DS2, DS3 and DS4 contains its own or inherent data in accordance with FIG. 5a as well as, respectively, three blocks of data DB1, DB2 and DB3, whereby the original data di are contained in a transferred block of data of the three other computer units, respectively, from another one of the three computer units REi.
The evaluation is then carried out in each computer unit respectively through a first comparison of the three data within each block of data for bitwise identity, and in a second comparison of the blocks of data DB1 to DB3 among one another, as well as with the respective original data in accordance with FIG. 5a, for identity, whereby congruent (i.e., bit-identical) and quasi-congruent identity (i.e., identity within a tolerance range) can be differentiated. When through the subsequent evaluation of the results of comparison, by means of the known Byzantine algorithm, a fault-containing computer unit is identified, the computer unit then produces and transfers a deactivating signal to the computer unit identified as being fault-containing. When this computer unit receives from all three other computer units a deactivating signal, this computer unit is deactivated.
Known computer units or assemblies formed therefrom in accordance with German Patent No. 44 01 168 C2 have, however, the disadvantage that due to the differing contents of the data storages (compare FIG. 5c of this application), as well as the distribution and the comparison of the data on a logical plane or data stream at a level or plane above the individual data, there is required for each computer unit an individual data evaluation, which leads thereto so that known computer units or, respectively, assemblies configured thereof operate rather slowly, since the transfer and evaluation of the sets of data or data sentences require a high computing effort.
One possible object of the present invention may be to provide a fault tolerant assembly of individual logic units or, respectively, computer units, these units per se, as well as a method of operating the assembly, being described above in this application, and which, respectively, operate essentially faster and essentially more reliably.
One possible embodiment of the present invention preferably teaches that this possible object can be accomplished with a logic unit of the type mentioned above in this application which is characterized thereby in that the registers are coupled withxe2x80x94each connected with one outputxe2x80x94the inputs and outputs, and that each register is capable of being in-read and out-read, independently of the position of the logic unit within the assembly, by means of a position-invariant relative identification.
Furthermore, at least one possible embodiment of the present invention preferably teaches a computer unit with such a logic unit, as well as teaching a fault tolerant assembly of at least 3F+1 identically configured ones of such logic units or, respectively, computer units, whereby the inputs and outputs of the logic units or, respectively, computer units, are connected with one another, such that corresponding registers of various logic units or, respectively, computer units comprise data of like relative identification of the origin and of the transmitting computer unit.
Finally, at least one possible embodiment of the present invention preferably teaches a method of operating an assembly in accordance with the invention with at least 3F+1 logic units or computer units according to the invention, wherein F is the amount of faults that can be tolerated simultaneously-as-to-time, with F+1 data distributing cycles, whereby in-read data during in-reading and during distribution are identified with a relative identification, whereby the relative identification of the data in corresponding registers and various logic units or, respectively, computer units, is essentially identical.
Throughout this application, the letter or numeral i may designate the origin of data d, that is, in relative identification, the computer unit into which the data were originally in-read, while the letter or numeral j may designate that computer unit RE from which these data were transferred.
Throughout this application, the term xe2x80x9cpertainingxe2x80x9d may mean xe2x80x9ccorresponding.xe2x80x9d
The relative identification may allow, in an essentially advantageous manner, the combining of identical computer units or logic units in an assembly. This makes it possible to operate computer units or logic units of an assembly at any desired position within the assembly, without it being necessary that adaptations be made. Furthermore, at least one possible embodiment of the present invention may allow the data distribution and the required data comparison exclusively by way of hardware and not by means of software, such that a fault tolerant assembly, in contrast with known assemblies, can be operated substantially faster and more reliably.
Preferably each computer unit comprises an identical logic unit associated with it. For the special case of F=1, each logic unit may have respectively 10 hardware shift registers, three inputs, which can be connected for in-reading of data sets or data sentences via first switch-over devices, with nine of such registers, as well as a further input which serves for in-reading of the original process data. Furthermore, each logic unit may have three outputs which are connectable, via respectively a second switch-over device, with all registers. Thereby each output of each logic unit is connected, respectively, to an input of such other logic unit, in such a manner that the data which are read-in into the first register of each logic unit are transferred by a first data distribution cycle into a register of each other logic unit. In a subsequent, second, data distribution cycle, data obtained during the first cycle from all other computer units are transferred from each register set into the other two respective register sets, which in the prior cycle were not senders of the specific data. Thereby the characterization of data and of the logic units is done by relative identification and cyclic modulo 4 check. The data may be distributed in such a way that these same registers of all register sets respectively have the same relative origin and respectively from a register set were transferred with essentially the same relative identification.
In at least one possible embodiment of the present invention, it is preferred that each logic unit has a plurality of deactivating lines, by means of which deactivating signals can be passed to further logic units or, respectively, deactivating signals can be received by further logic units, in the event that a fault has been recognized. Upon a completed deactivation, a re-activation of a logic unit, which may be particularly preferred, can be initiated. During re-activation, as well as during the initial activation of each logic unit, the logic units may be synchronized with the aid of cyclic data communication.
Essentially advantageously on the basis of a deactivating status, it may be decided whether data of a further unit are also to be excluded from data distribution and data evaluation or whether they are to be included.
The above-discussed embodiments of the present invention will be described further hereinbelow with reference to the accompanying figures. When the word xe2x80x9cinventionxe2x80x9d is used in this specification, the word xe2x80x9cinventionxe2x80x9d includes xe2x80x9cinventionsxe2x80x9d, that is, the plural of xe2x80x9cinventionxe2x80x9d. By stating xe2x80x9cinventionxe2x80x9d, Applicant does not in any way admit that the present application does not include more than one patentably and non-obviously distinct invention, and Applicant maintains that this application may include more than one patentably and non-obviously distinct invention. Applicant hereby asserts that the disclosure of this application may include more than one invention, and that these inventions may be patentable and non-obvious one with respect to the other.
Further details, features and advantages of the invention can be found in the following description of a preferred embodiment on the basis of the drawings.